The present invention relates generally to packet communication networks and, more particularly, to scheduling of packets for transmission on a communication link.
Communication networks transmit different types of traffic, such as voice, data or video traffic. These different types of traffic generally have different quality of service (QoS) requirements. The QoS required by a type of traffic is often determined by the nature of the traffic. Voice traffic has low communication bandwidth requirements but is intolerant of delays or information arriving out of order. The same is also true of video traffic, but video traffic also requires much higher bandwidths. Data transfer has different characteristics. Data transfer usually occurs in bursts involving periods where little bandwidth is required, and then periods where very high bandwidths are required. Delay and order are largely irrelevant in data transfers, the primary requirement is often speed.
Asynchronous Transfer Mode (ATM) allows for different types of traffic to be carried using a single network. In practice ATM networks dynamically allocate network resources to meet the different qualities of service required by each of the different types of traffic being carried by the network.
ATM networks comprise a number of nodes connected by communication links. The nodes communicate by sending information in cells of 53 bytes along a predetermined path through the network. The predetermined path is referred to as a virtual circuit. When nodes wish to communicate, they tell the network the QoS they require from the virtual circuit. They do this by specifying such metrics as acceptable cell loss rate, minimum throughput, maximum jitter and maximum delay. The network establishes a virtual circuit if it can guarantee that the specified QoS parameters will be met.
ATM networks determine if specified QoS requirements can be met by predicting a path through the network that is likely to meet the requirements and then interrogating the nodes along that path to establish whether the nodes can accommodate the connection. The virtual circuit is established if all of the nodes along the connection route guarantee that the specified QoS requirements will be met. This method of allocating the resources of an ATM network ensures that the network provides the precise needs of a traffic stream provided they are within the network's capacity.
At each node in a network, schedulers are responsible for the order in which received cells from a variety of sources are transmitted on an outgoing communication link. One method used on scheduling packet transmission is an Earliest Deadline First (EDF) method. EDF schedulers assign each incoming cell a time by which it must be transmitted based on its QoS requirements. The scheduler then selects the cell that is closest to exceeding its deadline as the next outgoing cell.
Implementation of EDF schedulers poses difficulties, however. For example, some cells may have rate based requirements, while other cells have delay based requirements. Moreover, the scheduler should also be able to quickly determine both where a cell should be placed in a queue, and which cell in a queue should be transmitted at any time.